package code.c04_String.KMP;

/**
 * @author thinkpad - 83start
 * @version v1.0
 * @create 2022/10/16 17:06
 * @package code.c04_String.KMP
 * @description 文件说明
 */

public class KMPTest {
    public static int KMP(String str, String sub, int pos) {
        // 非法约束
        if (str == null || sub == null) {
            return -1;
        }

        if (str.length() == 0 || sub.length() == 0) {
            return -1;

        }

        if (pos < 0 || pos >= str.length()) {
            return -1;
        }

        int i = pos; // 主串
        int j = 0; // 子串

        int[] next = new int[sub.length()];

        // 获取 next 数组
        getNext(sub, next);

        // 遍历主串 和 子串
        while (i < str.length() && j < sub.length()) {
            if (j == -1 || str.charAt(i) == sub.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
            }
        }

        if (j >= sub.length()) {
            return i - j;
        } else {
            return -1;
        }
    }

    private static void getNext(String sub, int[] next) {
        next[0] = -1;
        next[1] = 0;

        int i = 2;
        int k = 0;

        for (; i < sub.length(); i++) {
            if (k == -1 || sub.charAt(i - 1) == sub.charAt(k)) {
                next[i] = k + 1;
                k++;
                i++;
            } else {
                k = next[k];
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(KMP("ABASDFSDFSDSDFSDF","SDF",0));
    }
}
